The present invention relates to a packet switch for carrying out routing of a variable-length packet (or a frame) like an IP (Internet Protocol) packet, particularly, a large-capacity packet switch for achieving complex controls such as QoS (Quality of Service) control, drop control and multicast control of a variable-length packet, and to a scheduling device, a drop control circuit, a multicast control circuit, and a QoS control device that can be used for the large-capacity packet switch.
In recent years, along with a rapid distribution of Internet services, there has been an increasing demand for communication traffic. Particularly, it has been desired to realize large-capacity routers and switches of high speed having a Tbps (terabit/sec) class or above.
Conventionally, in a router device for processing variable-length packets like IP packets, there has been employed hardware for executing the packet forwarding processing in order to increase the processing speed. However, both software and hardware at only a low speed have been able to execute complex processing like QoS control, drop control and multicast control. Further, in ATM (Asynchronous Transfer Mode) switching, the QoS control, drop control and multicast control have basically been carried out for each fixed-length packet.
The software-based processing of a router device can be implemented by complex processing. However, with the increase in line speed, it has become difficult to achieve software processing at a speed equivalent to the line speed, which makes it difficult to achieve higher-speed and larger-capacity processing.
In the case of an ATM switching system, this system does not have a function of carrying out the QoS control, drop control and multicast control for each variable-length packet like the IP packet as the QoS control, drop control and multicast control are carried out for each fixed-length packet. There has been an attempt to carry out QoS control and drop control at a variable-length packet level by utilizing the variable-length packet identification of AAL5 in the ATM called GFR (Guaranteed Frame Rate). However, this system also uses a fixed-length packet unit called a cell for the packet switching and transfer. As it is necessary to realize all the nodes constituting a network by the ATM switching system, it is not possible to apply this system as a packet switch for carrying out the switching and transfer processing in IP packet unit.
Regarding the QoS control, WFQ (Weighted Fair Queuing) has been mainly known as a fair method of allocating bandwidth among variable-length packets of best effort class where bandwidth is not prescribed in advance.
The WFQ is based on GPS (Generalized Processor Sharing) for allocating a surplus area in proportion to the weight set to a queued connection. The GPS is a system of bandwidth allocation for distributing the read data volume so that the following equation (1) is always established for optional active connections (i) and (j) that use queues.S(i, τ, t)/S(j, τ, t)≧Φ(i)/Φ(j)  (1)
Where Φ(N) represents a weight of a connection N, and S (N, τ, t) represents a volume of data served for the connection N during a period [τ, t]. In the equation (1), the left side member becomes equal to the right side member when data of the connections (i) and (j) are both queued. It is assumed, for example, that weights have been allocated to connections #0, #1, #2 and #3 at the ratio of 0.1: 0.2: 0.4: 0.3, respectively. When only the connection #3 is non-active (that is, the packets are not queued) and all other connections are active, the reading bandwidth is allocated to the connections #0 to #2 excluding the connection #3 at the ratio of 0.1: 0.2: 0.4 respectively.
The GPS means bandwidth allocation basically in an infinitesimal unit. However, as the allocation is in a variable-length packet (a frame) unit in reality, the WFQ expands the GPS to a fair bandwidth allocation of a frame level.
According to WFQ, when a frame has arrived, an expected finish time F (i, k) when a packet of a k-th order in a flow i has arrived at a time t (i, k) and the frame length is L (i, k), is calculated based on the equation (2). Then, the data is read out sequentially starting from the smallest F.F(i, k)=max {F(i, k−1), t (i, k)}+L(i, k)/r(i)  (2)
Where r(i)=Φ(i)/ΣΦ×R. ΣΦ represents a total weight of queued connections, and R represents a rate of an output link.
In this case, r (i) changes each time when a packet has been read from a queue. Therefore, it is necessary to calculate F (i, k) repeatedly for all the connections. Further, it is necessary to hold the expected finish time F (i, k) for all the queued packets. Therefore, there has been a problem of an increase in the scale of hardware. To solve this problem, there has been proposed a system where, in place of real time, virtual time (a time counter of which notch changes according to the number of queued connections) is defined by equation (3), F (i, k) is re-defined by equation (4), the virtual time is re-calculated each time when ΣΦ and R have changed, and F (i, k) is calculated only once when a packet has arrived.Vt=V(τ)+(R/ΣΦ)(t−τ)  (3)F(i, k)=max {F(i, k−1), Vt(i, k)}+L(i, k)/Φ(i)  (4)
The use of virtual time can decrease the calculation volume. However, this has had a problem that it is difficult to control priorities of packets of the guaranteed bandwidth class for which a transfer rate has been prescribed and which need to be processed in real time.
Regarding the drop control, RED (Random Early Detection) has been known as an adaptive dropping system (Internet Society RFC 2309). In order to avoid a synchronization of a congested state, once congestion has occurred, this system carries out a random drop in a probability according to the state of congestion before buffers overflow. Based on this system, it is possible to drop the transmission rate at an early stage in a protocol that has a congestion control function like TCP (Transmission Control Protocol). It is also possible to obtain a stable throughput as the operations of all terminals are not synchronized.
However, as RED requires a random execution of dropping, the algorithm is complex and is implemented by software. Therefore, this system has not been designed for high-speed processing. Further, as the dropping is basically carried out when a frame (a variable-length packet) has arrived, the drop cannot be posted to a terminal until after all the data stored in the buffers have been swept out.
Regarding the multicast control, a buffer address management system has so far been realized for only the packet-by-packet operation of fixed-length packets. There has not yet been realized a control which takes into account a variable-length packet that consists of a plurality of continuous fixed-length packets.
It is, therefore, an object of the present invention to provide a large-capacity packet switch for executing complex controls such as QoS control, drop control and multicast control of variable-length packets by small-scale hardware with high-speed processing, and a scheduling device, a drop control circuit, a multicast control circuit, and a QoS control device that can be used for this large-capacity packet switch.